#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        
        // 奇数序号链表的头节点，这里是为了辅助，这个头节点是不存储任何数据的，
        ListNode *h1 = new ListNode(-1), *r1 = h1;
        // 偶数序号链表的头节点
        ListNode *h2 = new ListNode(-1), *r2 = h2;
        ListNode *p = head;
        // 遍历链表, 由于链表是有顺序的，所以链表的第一个元素就是奇数序号，第二个元素是偶数序号，交替变化
        while (p != nullptr)
        {
            // 给定的链表的头节点元素一定是奇数
            // 将奇数序号的头节点p连接到h1的末尾
            r1->next = p;
            r1 = p;
            // 下一个一定是偶数
            p = p->next;
            if (p != nullptr)
            {
                r2->next = p;
                r2 = p;
                p = p->next;
            }
            
        }
        // 将两个链表连接起来
        r1->next = h2->next;
        r2->next = nullptr;
        // 返回目标链表
        return h1->next;
    }
};

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next)
            cout << " -> ";
        head = head->next;
    }
    cout << " -> NULL" << endl;
}

int main() {
    // Test case 1: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    ListNode n1(1), n2(2), n3(3), n4(4), n5(5);
    n1.next = &n2; n2.next = &n3; n3.next = &n4; n4.next = &n5;

    Solution sol;
    ListNode* result1 = sol.oddEvenList(&n1);
    cout << "Test Case 1 Result: ";
    printList(result1);

    return 0;
}